﻿/************************************************************************
 * SMLib - State Model Library
 * Copyright (C) 2012-2013 Ali Khalili (khalili_DOT_ir_@SIGN_gmail_DOT_com)
 * **********************************************************************
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License (LGPL) published 
 * by the Free Software Foundation; either version 2.1 of the License, or (at your
 * option) any later version. This program is distributed without any
 * warranty. See the GNU Lesser General Public License for more details. 
 * ***********************************************************************
 * File         :     SMLib\Storage\MTBDD.cs
 * Description  :     Multi Terminal Binary Decision Diagram (MTBDD). This implementation is based on
 *                    [Mehmood, R. et.al, A Parallel Implicit Method for the Steady-State Solution of CTMCs, 2006]
 *                    to be used in solving CTMCs using gauss-seidle algorithm on a multi-core machine
 * Developer    :     (c) Sharzad Torabi (shahrzadtorabi@gmail.com)                   
 * Change log   :     -Jan 2012: some mofifications
 *                    -2011:  Initial version
 * To Do        :     1-Use this instead of previous class and structures (DONE!)
 *                    2-Remove the second algorithm for state space generation
 *                    3-On the fly computation of rewards
 ************************************************************************/
using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using SMLib.Utils;


namespace SMLib.Storage
{

//    /// <summary>
//    /// Multi Terminal Binary Decision Diagram (MTBDD)
//    /// <remarks>
//    /// This implementation is based on
//    /// [Mehmood, R. et.al, A Parallel Implicit Method for the Steady-State Solution of CTMCs, 2006]
//    /// to be used in solving CTMCs using gauss-seidle algorithm on a multi-core machine
//    /// </remarks>
//    /// </summary>
//    class MTBDD_StateSpace : CTMC_StateSpace
//    {
//        int blockCount;
//        public MTBDD_StateSpace(int blockCount)
//        {
//            this.blockCount = blockCount;
//        }
//
//        //#region Overriding virtual methods
//        //protected override IStateContainer newStateContainer(/*IStateContent*/object content)
//        //{
//        //    //Same as usual
//        //    return new CTMCState(states.Count, content);
//        //}
//
//        ///// <summary>
//        ///// 
//        ///// </summary>
//        ///// <param name="st"></param>
//        ///// <param name="tr"></param>
//        ///// <returns></returns>
//        //protected override ITransition newTransition(IStateContainer st, object tr)
//        //{
//        //    return new CTMCState.Transition((double)tr, (CTMCState)st);
//        //}
//
//        ///// <summary>
//        ///// 
//        ///// </summary>
//        ///// <param name="tr"></param>
//        ///// <param name="newTr"></param>
//        //protected override void UpdateTransition(IStateContainer src, ITransition tr, object newTr)
//        //{
//        //    ((CTMCState.Transition)tr).Rate += (double)newTr;
//        //}
//        //#endregion
//    }


    /// <summary>
    /// Store a CTMC as a Multi Terminal Binary Decision Diagram (MTBDD)
    /// </summary>
    public class MTBDD
    {
        #region Variables

        //Ali: Why All these stuff are static?
        //static 
        int blockNumber;//tedade block ha       

        //static 
        int[] data;
        //static 
        int count = -1;
        //static 
        int session = 0;

        //static 
        Hashtable ht;// = new Hashtable();
        ISqMatrix<double> ss;
        //int size, blockCount;

        //part1 MTBDD
        //static 
        //int[] val;// = new int[count + 1];

        //part2 MTBDD
        //static 
        int[] Start;
        //static 
        int[] column;
        //static 
        double[] value;
        //static 
        int[] blockCount_row;

        //for gauss-seidel
        //static 
        int blockCounter;//for X

        object[] o;
        #endregion

        public MTBDD(ISqMatrix<double> ss, int size, int blockCount)
        {
            this.ss = ss;
            //this.size = size;
            //this.blockCount = blockCount;

            if (ht == null)
                ht = new Hashtable();
            else
                ht.Clear();
            //val = new int[count + 1];

            //ss.Save("c:\\stateSpaceRecduced.xml");
            blockNumber = size / blockCount;

            //color = new int[blockNumber];

            //processed = new int[blockNumber];
            //unprocessed = new int[blockNumber];
            blockCount_row = new int[blockNumber];
            data = new int[blockNumber];

            ht = ZeroBlocks(size, size / blockCount, blockCount);
            o = new object[5];
            o[0] = ht;
            o[1] = data;
            o[2] = blockCount_row;
            //return o;
        }

        public object[] MTBDDObjects
        {
            get
            {
                return o;
            }
        }

        //public object[] BlockSize(int size, int blockCount, ICTMCMatrix ss)
        //{
        //    this.ss = ss;
        //    //ss.Save("c:\\stateSpaceRecduced.xml");
        //    blockNumber = size / blockCount;

        //    //color = new int[blockNumber];

        //    //processed = new int[blockNumber];
        //    //unprocessed = new int[blockNumber];
        //    blockCount_row = new int[blockNumber];
        //    data = new int[blockNumber];

        //   ht= ZeroBlocks(size, size / blockCount, blockCount);
        //   object []o = new object[5];
        //   o[0] = ht;
        //   o[1] = data;
        //   o[2] = blockCount_row;
        //   return o;
        //}

        Hashtable ZeroBlocks(int size, int k, int y)
        {

            bool flag = false;
            int t = -1;
            int row = -y;
            int r = 0;
            int c = 0;
            int temp = y;

            while (row < size - y)
            {
                blockCounter = 0;
                row = row + y;
                c = 0;
                r = 0;
                temp = y;

                while (c < k)
                {
                    t++;
                    flag = false;
                    for (int i = row; i < row + y; i++)
                    {
                        for (int j = r; j < temp; j++)
                        {
                            //Ali: instead, use statespace[i,j]
                            if (ss.CTMCRate(i, j) != 0)
                            //Commented by Ali:]if (edge[i, j] != 0)
                            {
                                flag = true;
                                i = row + y;
                                break;
                            }

                        }

                    }
                    if (flag == true)
                    {
                        blockCounter++;

                        ArrayList al = new ArrayList();
                        value = new double[y * y];
                        Start = new int[y + 1];
                        column = new int[y * y];
                        int blocksize = y;
                        al = Save(row / y, c, count + 1, 0, blocksize);

                        ht.Add(session, al);//foeach nonzero block that is saved with CSR format we add one element to the hashtable
                        session += 1;

                    }
                    r = r + y;
                    c = c + 1;
                    temp = temp + y;
                }
                blockCount_row[row / y] = blockCounter;
                data[row / y] = blockCounter;
                if (y != 0 && (row / y) > 0)
                    data[row / y] += data[row / y - 1];
            }
            return ht;
        }

        ArrayList Save(int blockRow, int blockColumn, int size, int startIndex, int blocksize)
        {
            //پيمايش ماتريس اوليه بزرگ و خلوت و يافتن مقادير غيرصفر آن و ذخيره سازي آنها به فرمت سي اس آر در داخل بلاكها
            for (int i = 0; i < Start.Length; i++)
                Start[i] = -1;

            int index = 0;
            int temp = -1;
            int counter = 0;
            for (int i = blocksize * blockRow; i < blocksize * blockRow + blocksize; i++)
            {
                for (int j = blocksize * blockColumn; j < blocksize * blockColumn + blocksize; j++)
                {
                    //Ali: Instead, use statespace[i,j]
                    if (ss.CTMCRate(i, j) != 0)
                    //Commented by Ali:if (edge[i, j] != 0)
                    {
                        value[index] = ss.CTMCRate(i, j); //Commented by Ali:(double)edge[i, j];

                        column[index] = j;
                        if (temp != i)
                        {
                            Start[i - blockRow * blocksize] = counter;
                            startIndex++;
                        }
                        temp = i;

                        index++;
                        counter++;
                    }

                }
            }
            Start[blocksize] = counter;//add one more start to end of the array
            ArrayList AL = new ArrayList();
            //AL is used to save nonzero elemnts in CSR format in the blocks
            AL.Add(value);
            AL.Add(column);
            AL.Add(Start);
            AL.Add(blockRow);
            AL.Add(blockColumn);
            AL.Add(false);


            return AL;


        }

    }
}